package com.eric.study.jobflow.graph;

import lombok.NonNull;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <p> Digraph. 有向图存储对象，使用邻接表存储边。
 *
 * <p>
 * change history:
 *
 * <pre>
 * date         defect       person          comments
 * --------------------------------------------------------------------------------
 * 2023/8/31    ********     Eric    create file.
 * </pre>
 *
 * @author Eric
 * @date 2023/8/31 10:18
 * @copyright 2023, FA Software (Shanghai) Co., Ltd. All Rights Reserved.
 * @since 1.0.0
 */
public class Digraph<E> {

    /**
     * 边个数
     */
    private int edge;

    /**
     * 有向图顶点集合
     */
    private final Set<E> vertices;

    /**
     * 有向图边集合
     */
    private final Map<E, Deque<E>> adjacency;

    public Digraph() {
        this.edge = 0;
        this.vertices = new HashSet<>();
        this.adjacency = new HashMap<>();
    }

    /**
     * 向有向图中添加边，由顶点 v -> other
     *
     * @param v     顶点v
     * @param other 顶点other
     * @author Eric
     * @date 2023/8/31 10:24
     * @since 1.0.0
     */
    public void addEdge(@NonNull E v, E other) {
        this.vertices.add(v);
        if (null != other) {
            this.vertices.add(other);
            // 添加边
            this.adjacency.computeIfAbsent(v, k -> new LinkedList<>()).add(other);
            this.edge++;
        }
    }

    /**
     * 判断指定的边（由顶点 v -&gt; other ）是否已经存在
     *
     * @param v     顶点v
     * @param other 顶点 other
     * @return 如果边存在，返回 {@code true}；否则，返回 {@code false}
     * @author Qiheng Zhang
     * @date 2023/9/1 09:30
     * @since 1.0.0
     */
    public boolean hasEdgeAlreadyExisted(E v, E other) {
        if (Objects.nonNull(this.adjacency.get(v))) {
            return this.adjacency.get(v).contains(other);
        } else {
            return false;
        }
    }

    /**
     * 获取有向图中的边数量
     *
     * @return 边数量
     * @author Eric
     * @date 2023/8/31 10:26
     * @since 1.0.0
     */
    public int edge() {
        return this.edge;
    }

    /**
     * 获取顶点 {@code v} 的所有邻接顶点
     *
     * @param v 顶点 v
     * @return 所有邻接顶点
     * @author Eric
     * @date 2023/8/31 10:27
     * @since 1.0.0
     */
    public Deque<E> adjacencyVertices(E v) {
        return Optional.ofNullable(this.adjacency.get(v)).orElseGet(LinkedList::new);
    }

    /**
     * 获取有向图中所有的顶点
     *
     * @return 顶点集合
     * @author Eric
     * @date 2023/8/31 10:29
     * @since 1.0.0
     */
    public Set<E> allVertices() {
        return this.vertices.stream().filter(Objects::nonNull).collect(Collectors.toSet());
    }

    /**
     * 反转有向图。
     *
     * <pre>
     *     原始有向图： A -> B -> C
     *     反转图结果： C -> B -> A
     * </pre>
     *
     * @return 反转结果
     * @author Eric
     * @date 2023/8/31 10:31
     * @since 1.0.0
     */
    public Digraph<E> reverse() {
        Digraph<E> ret = new Digraph<>();
        for (E v : this.vertices) {
            if (this.vertices.isEmpty()) {
                ret.addEdge(v, null);
            } else {
                for (E w : this.adjacency.get(v)) {
                    if (Objects.nonNull(w)) {
                        ret.addEdge(w, v);
                    }
                }
            }
        }
        return ret;
    }

    public boolean hasCycle() {
        return new DigraphCycle<>(this).hasCycle();
    }

    public List<E> order() {
        if (!hasCycle()) {
            return new DepthFirstOrder<>(this).reversePost().stream().filter(Objects::nonNull).toList();
        }
        return Collections.emptyList();
    }

    /**
     * 图环检测工具类
     *
     * @param <E> 顶点类型限制
     */
    private static final class DigraphCycle<E> {

        /**
         * 记录顶点是否已经被搜过了
         */
        private final Map<E, Boolean> marked;

        /**
         * 标记图中是否有环
         */
        private boolean hasCycle;

        /**
         * 记录顶点是否在搜索队列中
         */
        private final Set<E> onStack;

        private DigraphCycle(Digraph<E> g) {
            this.marked = new HashMap<>();
            this.hasCycle = false;
            this.onStack = new HashSet<>();

            // 遍历所有的顶点进行深度搜索
            for (E v : g.allVertices()) {
                // 如果顶点在 marked 中不存在或者为 false 时，则表示未被搜索过，则进行深度搜索
                if (this.marked.get(v) == null || !this.marked.get(v)) {
                    dfs(g, v);
                }
            }
        }

        /**
         * 图深度搜索方法
         *
         * @param g 搜索的图
         * @param v 搜索的顶点
         * @author Eric
         * @date 2023/8/31 10:40
         * @since 1.0.0
         */
        private void dfs(Digraph<E> g, E v) {
            // 标记 v 已经搜过了
            this.marked.put(v, true);

            // 添加到搜索队列中
            this.onStack.add(v);

            // 遍历当前顶点的所有邻接顶点
            for (E w : g.adjacencyVertices(v)) {
                // 如果 w 未被搜索过，则递归
                if (this.marked.get(w) == null || !this.marked.get(w)) {
                    dfs(g, w);
                }

                // 检查 w 顶点是否已经在搜索队列中
                if (this.onStack.contains(w)) {
                    this.hasCycle = true;
                    return;
                }
            }

            // 递归返回时清空搜索队列
            this.onStack.remove(v);
        }

        private boolean hasCycle() {
            return this.hasCycle;
        }
    }

    /**
     * 有向图顶点排序工具
     *
     * @param <E> 元素类型限制
     */
    private static final class DepthFirstOrder<E> {

        /**
         * 记录顶点是否被搜索过
         */
        private final Set<E> searched;

        /**
         * 使用栈保存排序结果
         */
        private final LinkedList<E> stack;

        public DepthFirstOrder(Digraph<E> g) {
            this.searched = new HashSet<>();
            this.stack = new LinkedList<>();

            for (E v : g.allVertices()) {
                // 如果顶点 v 未被搜索过，则进行深度搜索
                if (!this.searched.contains(v)) {
                    dfs(g, v);
                }
            }

        }

        /**
         * 图深度搜索方法
         *
         * @param g 搜索的图
         * @param v 搜索的顶点
         * @author Eric
         * @date 2023/8/31 10:47
         * @since 1.0.0
         */
        private void dfs(Digraph<E> g, E v) {
            // 标记 v 已经被搜索过了
            this.searched.add(v);

            // 遍历顶点 v 的所有邻接顶点
            for (E w : g.adjacencyVertices(v)) {
                // 如果顶点 w 未被搜索过，则递归
                if (!this.searched.contains(w)) {
                    dfs(g, w);
                }
            }
            // 当前顶点已经没有邻接顶点了，则将顶点放入栈中
            this.stack.push(v);
        }

        /**
         * 获取顶点排序结果
         *
         * @return 排序结果
         * @author Eric
         * @date 2023/8/31 10:51
         * @since 1.0.0
         */
        private List<E> reversePost() {
            return this.stack;
        }
    }

}
